import collections
from typing import List


class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        n = len(grid)

        new_grid = [
            [[0] * (n - 1) for _ in range(n)],  # 蛇横着时的位置：n行+(n-1)列
            [[0] * n for _ in range(n - 1)]  # 蛇竖着时的位置：(n-1)行+n列
        ]

        # 计算以上两种位置是否能够到达
        for i1 in range(n):
            for j1 in range(n):
                if grid[i1][j1] == 1:
                    if j1 < n - 1:
                        new_grid[0][i1][j1] = 1
                    if j1 > 0:
                        new_grid[0][i1][j1 - 1] = 1
                    if i1 > 0:
                        new_grid[1][i1 - 1][j1] = 1
                    if i1 < n - 1:
                        new_grid[1][i1][j1] = 1

        # print("GRID1")
        # for row in new_grid[0]:
        #     print(row)

        # print("GRID2")
        # for row in new_grid[1]:
        #     print(row)

        # 蛇的移动：可以移动到new_grid[0]和new_grid[1]中不为1的位置
        # 蛇的转身：当new_grid[0]和new_grid[1]中当前坐标均存在且均为0，且下一个值也为0就可以互换
        visited = {(0, 0, 0)}
        queue = collections.deque([(0, 0, 0)])
        distance = 0
        while queue:
            for _ in range(len(queue)):
                k1, i1, j1 = queue.popleft()
                if (k1, i1, j1) == (0, n - 1, n - 2):
                    return distance

                if (k1 == 0 and i1 + 1 < n) or (k1 == 1 and i1 + 1 < n - 1):
                    k2, i2, j2 = k1, i1 + 1, j1
                    if new_grid[k2][i2][j2] == 0 and (k2, i2, j2) not in visited:
                        visited.add((k2, i2, j2))
                        queue.append((k2, i2, j2))

                if (k1 == 0 and j1 + 1 < n - 1) or (k1 == 1 and j1 + 1 < n):
                    k2, i2, j2 = k1, i1, j1 + 1
                    if new_grid[k2][i2][j2] == 0 and (k2, i2, j2) not in visited:
                        visited.add((k2, i2, j2))
                        queue.append((k2, i2, j2))

                if ((k1 == 0 and i1 + 1 < n and new_grid[0][i1 + 1][j1] == 0) or
                        (k1 == 1 and j1 + 1 < n) and new_grid[1][i1][j1 + 1] == 0):
                    k2, i2, j2 = 1 - k1, i1, j1
                    if new_grid[k2][i2][j2] == 0 and (k2, i2, j2) not in visited:
                        visited.add((k2, i2, j2))
                        queue.append((k2, i2, j2))

            distance += 1

        return -1


if __name__ == "__main__":
    # 11
    print(Solution().minimumMoves(grid=[[0, 0, 0, 0, 0, 1],
                                        [1, 1, 0, 0, 1, 0],
                                        [0, 0, 0, 0, 1, 1],
                                        [0, 0, 1, 0, 1, 0],
                                        [0, 1, 1, 0, 0, 0],
                                        [0, 1, 1, 0, 0, 0]]))

    # 9
    print(Solution().minimumMoves(grid=[[0, 0, 1, 1, 1, 1],
                                        [0, 0, 0, 0, 1, 1],
                                        [1, 1, 0, 0, 0, 1],
                                        [1, 1, 1, 0, 0, 1],
                                        [1, 1, 1, 0, 0, 1],
                                        [1, 1, 1, 0, 0, 0]]))

    # 测试用例39/42 : -1
    print(Solution().minimumMoves(
        [[0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
         [0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0],
         [0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0],
         [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
         [0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0],
         [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0],
         [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
         [0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0],
         [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
         [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
         [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
         [1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
         [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
         [1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1],
         [0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]))
